package com.maishi.programmer.jainzhioffer;

import java.util.ArrayList;

/**
 * Created by brossdong on 2018/4/3.
 * 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
 * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 */
public class TestProblem34 {

    /**
     * 先构造树
     */
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode (int val) {
            this.val = val;
        }
    }

    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> list = new ArrayList<>();
    //记录路径的值
    int num = 0;

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        //判断是否是叶子节点
        boolean isLeaf = root.left == null && root.right == null;
        num += root.val;
        list.add(root.val);
        if (root == null) return null;
        //等于目标值  且  是叶子结点
        if (num == target && isLeaf) {
            ArrayList<Integer> treeList = new ArrayList<>();
            for (int i = 0;i < list.size();i++) {
                treeList.add(list.get(i));
            }
            result.add(treeList);
        }
        //小于目标值  且  不是叶子结点 ==>左子树
        if(num < target && root.left != null){
            FindPath(root.left,target);
        }
        //小于目标值  且  不是叶子结点  ==>右子树
        if( num < target && root.right != null){
            FindPath(root.right,target);
        }
        num -= root.val;
        list.remove(list.size()-1);
        return result;
    }

    public static void main(String[] args) {

    }


}
